package uva.string;

import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 
 * @author shivendra
 * DP[i, j] = if(x(i) == x(j)) DP[i-1, j+1] +2 else max(DP[i-1, j], DP[i, j-1])
 * In this problem its convinoient to do transition as  substring than prefix or suffix
 */
public class DP_11151 {
	public static void main(String[] args) {
		PrintWriter pw = new PrintWriter(System.out);
		Scanner scn = new Scanner(System.in);
		int cases = Integer.parseInt(scn.nextLine());
		while(cases-- >0){
			String str = scn.nextLine();
			int[][] dp = new int[str.length()][str.length()];
			//base case
			for(int i=0; i<str.length(); i++){
				for(int j=0; j<str.length(); j++){
					if(i == j)
					dp[i][j] = 1;
					if( j-i == 1){
						dp[i][j] = str.charAt(i) ==str.charAt(j) ? 2 : 1;
					}
				}
			}
			for(int j=2; j<str.length(); j++){
				for(int i=0; i<str.length()-j; i++){
					if(str.charAt(i) == str.charAt(i+j))
					dp[i][i+j] = dp[i+1][i+j-1] +2;
					else
						dp[i][i+j] = Math.max(dp[i][i+j-1], dp[i+1][i+j]);
				}	
			}
		pw.println(str.length() >0 ? dp[0][str.length()-1] : 0);
		}
		pw.close();
	}
}
